/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package uml.graph;

import java.text.DecimalFormat;
import java.util.ArrayList;  

/**
 *
 * @author Paloma
 */     

public class Grafo {  

	private ArrayList<Aresta> arestas = new ArrayList<Aresta>(); 
	private ArrayList<Vertice> 	vertices = new ArrayList<Vertice>();  
	private double [][]matrizAdjacencia;  
	private double [][] matrizIncidencia;  
	private double [][] matrizD;
	private double [][] matrizLaplace;


	//  Cria um grafo usando matriz de adjacencia  
	public Grafo(){} 

	//  Cria um grafo usando matriz de adjacencia  
	public Grafo(ArrayList<Vertice> vertices, ArrayList<Aresta> arestas){
		this.vertices = vertices;  
		this.arestas = arestas;

		updateMatrizAdjacencias();
		criarMatrizD();
		criarMatrizLaplace();
	} 

	public Vertice addVertice(Vertice v){  
		vertices.add(v);  
		return(v);  
	}  

	private ArrayList<Vertice> visit(Vertice vertice, ArrayList<Vertice> visited){
		
		visited.add(vertice);
		
		ArrayList<Vertice> adj = getAdjacencias(vertice);
		
		for(int i = 0; i < adj.size(); i++){
			if(!visited.contains(adj.get(i))){
				visit(adj.get(i), visited);
			}
		}
		
		return visited;
	}
	
	public boolean isConnected(){
		return visit(getVertice(0), new ArrayList<Vertice>()).size()==getQtdVertices();
	}

	public  Aresta addAresta(Vertice _v1, Vertice _v2, int peso){  
		if(getArestaEntreVertices(_v1,_v2) == null){  
			Aresta aresta = new Aresta(_v1,_v2, peso);  
			arestas.add(aresta);  
			this.updateMatrizAdjacencias();  
			this.updateMatrizIncidencias();  
			return(aresta);  

		}  
		return(null);  
	}   

	public  Vertice getVertice(int i){  
		return((Vertice)vertices.get(i));  
	}  

	public synchronized  Aresta getAresta(int i){  
		return((Aresta)arestas.get(i));  
	}  

	public Aresta getArestaEntreVertices(Vertice _v1, Vertice _v2){  
		Aresta aresta;  
		for(int i=0; i < arestas.size(); i++){
			aresta = getAresta(i);  
			if(aresta.contemAresta(_v1,_v2)){ 
				return(aresta);  
			}
		}  
		return(null);  
	}

	public ArrayList<Vertice> getAdjacencias(Vertice v){  
		Aresta aresta;  
		ArrayList<Vertice> adjacencias = new ArrayList<Vertice>();  
		for(int i=0;i<arestas.size();i++){  
			aresta = this.getAresta(i);
			if(aresta != null){
				if(aresta.getvorigem() == v){  
					adjacencias.add(aresta.getvdestino()); 
					//System.out.println("get Adjacencias destino"+ aresta.getRotulo());
				}  
				if(aresta.getvdestino() == v){  
					adjacencias.add(aresta.getvorigem());
					//System.out.println("get Adjacencias origem "+ aresta.getRotulo());
				}
			}
		}  

		return(adjacencias);  
	}  

	public synchronized int getQtdVertices(){  
		return(vertices.size());  
	} 

	public synchronized int getQtdArestas(){  
		return(arestas.size());  
	}

	public  void updateMatrizAdjacencias(){  
		Vertice vertice;  
		Vertice verticeAux;  
		ArrayList<Vertice> v_adjacencias;  
		matrizAdjacencia = new double[vertices.size()][vertices.size()];  

		for(int i=0; i < vertices.size(); i++){  
			
			for(int j=0; j < vertices.size(); j++){  
				
				vertice = vertices.get(i);
				verticeAux = vertices.get(j);
				Aresta aresta = getArestaEntreVertices(vertice, verticeAux);
				if(aresta!=null){
					matrizAdjacencia[i][j] = aresta.getPeso();	
				} else {
					matrizAdjacencia[i][j] = 0;
				}
				
				
			}
			
		}
		
		/*
		for(int i=0; i < vertices.size(); i++){  
			vertice = getVertice(i);  
			v_adjacencias = getAdjacencias(vertice);  
			for(int j=0; j < v_adjacencias.size(); j++){  
				verticeAux = (Vertice) v_adjacencias.get(j);
				int index = getIndex(verticeAux);
				if(index != -1)
					matrizAdjacencia[i][index] = getArestaEntreVertices(vertice, verticeAux).getPeso();  
			}  
		}  
		*/
	}

	private int getIndex(Vertice v){
		for(int i=0; i < vertices.size(); i++)
			if(vertices.get(i).equals(v))
				return i;
		return -1;
	}

	private  void updateMatrizIncidencias(){  
		Aresta aresta;  
		matrizIncidencia = new double[vertices.size()][arestas.size()];  

		for(int j=0;j<arestas.size();j++){  
			aresta = this.getAresta(j);

			int index = getIndex(aresta.getvorigem());
			if(index != -1)
				matrizIncidencia[index][j] = 1;

			int index2 = getIndex(aresta.getvdestino());
			if(index2 != -1)
				matrizIncidencia[index2][j] = 1;  
		}  
	} 

	public void criarMatrizD(){
		matrizD = new double[vertices.size()][vertices.size()];
		int grau=0;
		for(int i=0;i<vertices.size();i++){
			for(int j=0;j<vertices.size();j++){
				grau += matrizAdjacencia[j][i];
			}
			matrizD[i][i] = grau;  
			grau=0;
		}
	}

	public void criarMatrizLaplace(){
		matrizLaplace = new double [vertices.size()][vertices.size()];
		for (int i =0;i<vertices.size();i++){
			for(int j =0;j<vertices.size();j++){
				matrizLaplace [i][j] = matrizD[i][j] - matrizAdjacencia[i][j];
			}       
		}

	}

	public String imprimeMatrizAdjacencia(Grafo grafo){
		String saida = "";
		for(int i = 0; i < vertices.size(); i++)   {
			for(int j = 0; j < matrizAdjacencia[i].length; j++)    {  
				saida = saida + new DecimalFormat("##	").format(matrizAdjacencia[i][j]) + " ";
				System.out.print(new DecimalFormat("##	").format(matrizAdjacencia[i][j]));
			}
			saida = saida + "\n";
			System.out.println("");  
		}

		return saida;
	} 

	public String imprimeMatrizIncidencia(Grafo grafo){
		String saida = "";
		for(int i = 0; i < vertices.size(); i++)   {  
			for(int j = 0; j < matrizIncidencia[i].length; j++)    {
				saida = saida + new DecimalFormat("##	").format(matrizIncidencia[i][j]) + " ";
				System.out.print(new DecimalFormat("##	").format(matrizIncidencia[i][j]));  
			}
			saida = saida + "\n";
			System.out.println("");  
		}

		return saida;
	}

	public String imprimeMatrizD(){
		String saida = "";
		for (int i =0;i<vertices.size();i++){
			for(int j=0;j<matrizD[i].length;j++){
				System.out.print(new DecimalFormat("##	").format(matrizD[i][j]));
				saida = saida + new DecimalFormat("##	").format(matrizD[i][j]) + " ";
			}
			saida = saida + "\n";
			System.out.println("");  
		}
		return saida;
	}

	public String imprimeMatrizLaplace(){
		String saida = "";
		for (int i =0;i<vertices.size();i++){
			for(int j=0;j<matrizLaplace[i].length;j++){
				saida = saida + new DecimalFormat("##	").format(matrizLaplace[i][j])+ " ";
				System.out.print(new DecimalFormat("##	").format(matrizLaplace[i][j]) + " "); 
			}
			saida = saida + "\n";
			System.out.println("");  
		}
		return saida;
	}

	public void imprimeListaVertices(){
		for (int i =0;i<vertices.size();i++){
			System.out.println("Esse e o vertice " + vertices.get(i).toString());
		}
	}

	public void imprimeListaArestas(){
		for (int i =0;i<arestas.size();i++){
			System.out.println("Esse e a aresta " + arestas.get(i).toString());
		}
	}

	public double [][] getMatrizLaplace(){
		return matrizLaplace;
	}

	public Vertice existeVertice(ArrayList<Vertice> vertices,String rotulo){
		Vertice aux=null;
		for (int i =0;i<vertices.size();i++){
			if (vertices.get(i).getRotulo().equals(rotulo)) {
				aux= vertices.get(i);
			} 
		}
		return aux;
	}

	public ArrayList<Aresta> getArestas() {
		return new ArrayList<Aresta>(arestas);
	}

}


